home *** CD-ROM | disk | FTP | other *** search
/ MacWorld 1999 November / Macworld (1999-11).dmg / Updaters / WhiteCap 3.0.4 / WhiteCap Source.sit / WhiteCap Source / Common / math / Expression.cpp < prev    next >
C/C++ Source or Header  |  1999-08-22  |  12KB  |  478 lines
  1. #include "Expression.h"
  2.  
  3. #include "ExpressionDict.h"
  4. #include "ExprVirtualMachine.h"
  5.  
  6.  
  7. #if EG_WIN
  8. #include "EgOSUtils.h"
  9. #endif
  10.  
  11.  
  12.  
  13.  
  14.  
  15.  
  16.  
  17. #define __collapseTwo                                                            \
  18.     highestPriority = 0;                                                        \
  19.     for ( i = 0; i < numExps-1; i++ ) {                                            \
  20.         priority = oper[ i ] & 0x0F00;                                            \
  21.         if ( priority > highestPriority ) {                                        \
  22.             highestPriority    = priority;                                            \
  23.             collapse        = i;                                                \
  24.         }                                                                        \
  25.     }                                                                            \
  26.     i = collapse;                                                                \
  27.     inVM.DoOp( expr[ i ], expr[ i + 1 ], oper[ i ] & 0xFF );                    \
  28.     inVM.DeallocReg( expr[ i + 1 ] );                                            \
  29.     numExps--;                                                                    \
  30.     oper[ i ] = oper[ i+1 ];                                                    \
  31.     for ( i++; i < numExps; i++ ) {                                                \
  32.         oper[ i ] = oper[ i+1 ];                                                \
  33.         expr[ i ] = expr[ i+1 ];                                                \
  34.     }
  35.  
  36.  
  37.  
  38. //    Pre:    All whitespace and illegal chars are removed
  39. //    Pre:    Parens balence & all letters are capitalized
  40. //    Note:    I normally don't write such huge, non-compartmentalized code, but speed is important
  41. //    Post:    Allocates a register for the return value and returns that register
  42. int Expression::Compile( char* inStr, long inLen, ExpressionDict& inDict, ExprVirtualMachine& inVM ) {
  43.     bool            hasLetters = false;
  44.     float*            floatPtr, val, **fcnPtr;
  45.     long            highestPriority, priority, i, numExps = 0, startPos = 0;
  46.     long            fcnCall, collapse, c, pos, parens = 0, firstParen = -1, size;
  47.     short            oper[ 4 ];
  48.     short            expr[ 4 ];
  49.     
  50.     // Catch a negated expression.  Make it the same as 0-...
  51.     if ( inLen > 0 && *inStr == '-' ) {
  52.         expr[ 0 ] = inVM.AllocReg();
  53.         oper[ 0 ] = 0x100 | '-';
  54.         inVM.Loadi( 0.0, expr[ 0 ] );
  55.         numExps = 1;
  56.         inStr++;
  57.         inLen--;
  58.     }
  59.             
  60.     // Make a pass thru of the string, finding the starts and ends of all root exprs
  61.     for ( pos = 0; pos < inLen; pos++ ) {
  62.         c = inStr[ pos ];
  63.         
  64.         if ( c == '(' ) {
  65.             if ( firstParen < 0 )
  66.                 firstParen = pos;
  67.             parens++;  }
  68.         else if ( c == ')' )
  69.             parens--;
  70.     
  71.         // Don't consider any chars if we're not at the root level        
  72.         if ( parens == 0 ) {
  73.             
  74.             if ( c >= 'A' && c <= 'Z' )
  75.                 hasLetters = true;
  76.         
  77.             // Operators are what separate exprs
  78.             switch ( c ) {    
  79.                 case '-':
  80.                 case '+':    priority = 0x0100;    goto doOp;
  81.                 case '/':
  82.                 case '%':
  83.                 case '*':    priority = 0x0200;    goto doOp;
  84.                 case '^':    priority = 0x0300;
  85.  
  86.                     // Close cur expr    
  87. doOp:                if ( pos > startPos && pos + 1 < inLen ) {
  88.                             
  89.                         // Recurse
  90.                         expr[ numExps ] = Compile( inStr + startPos, pos - startPos, inDict, inVM );
  91.                         oper[ numExps ] = c | priority;
  92.                         numExps++;
  93.                         startPos = pos + 1;
  94.                         
  95.                         // 4 exprs, given three priority operators, 4 exprs guaruntees we can collapse two into one expr
  96.                         if ( numExps == 4 ) {
  97.                             __collapseTwo
  98.                         }
  99.                     }
  100.             }
  101.         }
  102.     }
  103.  
  104.  
  105.     // Detect base case (ie, whole string is an expr)
  106.     if ( numExps == 0 ) {
  107.             
  108.         // See if we found a fcn call or an unneeded paren pair: (...)
  109.         if ( firstParen >= 0 && firstParen <= 4 ) {
  110.  
  111.             // Eval what's inside the parens
  112.             expr[ 0 ] = Compile( inStr + firstParen + 1, inLen - firstParen - 2, inDict, inVM );
  113.         
  114.             // if we have a fcn (as opposed to just a paren pair)
  115.             if ( firstParen > 0 ) { 
  116.             
  117.                 // Translate the string of the fcn to a (one byte) sub op code number
  118.                 fcnCall = *((long*) inStr);
  119.                 #if EG_WIN
  120.                 fcnCall = EgOSUtils::RevBytes( fcnCall );
  121.                 #endif
  122.                 switch ( fcnCall ) {
  123.                     case 'SQRT':    fcnCall = cSQRT;        break;
  124.                     case 'ATAN':    fcnCall = cATAN;        break;
  125.                     case 'ABS(':    fcnCall = cABS;            break;
  126.                     case 'SIN(':    fcnCall = cSIN;            break;
  127.                     case 'COS(':    fcnCall = cCOS;            break;
  128.                     case 'TAN(':    fcnCall = cTAN;            break;
  129.                     case 'LOG(':    fcnCall = cLOG;            break;
  130.                     case 'EXP(':    fcnCall = cEXP;            break;
  131.                     case 'SQR(':    fcnCall = cSQR;            break;
  132.                     case 'SQWV':    fcnCall = cSQWV;        break;
  133.                     case 'POS(':    fcnCall = cPOS;            break;
  134.                     case 'RND(':    fcnCall = cRND;            break;
  135.                     case 'SGN(':    fcnCall = cSGN;            break;
  136.                     case 'TRWV':    fcnCall = cTRWV;        break;
  137.                     case 'CLIP':    fcnCall = cCLIP;        break;
  138.                     case 'SEED':    fcnCall = cSEED;        break;
  139.                     default: {
  140.                         fcnCall = 0;
  141.                         UtilStr temp( inStr, firstParen );
  142.                         fcnPtr = inDict.LookupFunc( temp, size );
  143.                         inVM.UserFcnOp( expr[ 0 ], fcnPtr, size );
  144.                     }
  145.                 }
  146.                 if ( fcnCall )
  147.                     inVM.MathOp( expr[ 0 ], fcnCall );  
  148.             } }
  149.         
  150.         // Catch the case where we have a number/immediate
  151.         else if ( ! hasLetters ) {
  152.             val = UtilStr::GetFloatVal( inStr, inLen );
  153.             expr[ 0 ] = inVM.AllocReg();  
  154.             inVM.Loadi( val, expr[ 0 ] ); }
  155.             
  156.         // At this point we assume it's an identifier, so we'll look up its value
  157.         else {
  158.             UtilStr temp;
  159.             temp.Assign( inStr, inLen );
  160.             expr[ 0 ] = inVM.AllocReg();
  161.             floatPtr = inDict.LookupVar( temp );
  162.             if ( floatPtr )
  163.                 inVM.Loadi( floatPtr, expr[ 0 ] );
  164.         } }
  165.         
  166.     // If there more than one expression
  167.     else {
  168.                 
  169.         // Finish the current expr
  170.         if ( startPos < inLen ) {
  171.             expr[ numExps ] = Compile( inStr + startPos, inLen - startPos, inDict, inVM );
  172.             numExps++;
  173.         }
  174.         
  175.         // When there'll be no more exprs, we're free to collapse all the exprs into one
  176.         while ( numExps > 1 ) {
  177.             __collapseTwo
  178.         }
  179.     }
  180.                 
  181.     return expr[ 0 ];
  182. }
  183.  
  184.  
  185.  
  186.  
  187.  
  188. /*
  189.  
  190.  
  191.  
  192.  
  193.  
  194.  
  195.  
  196. #define __collapseTwo                                                            \
  197.     highestPriority = 0;                                                        \
  198.     for ( i = 0; i < numExps-1; i++ ) {                                            \
  199.         priority = oper[ i ] & 0x0F00;                                            \
  200.         if ( priority > highestPriority ) {                                        \
  201.             highestPriority    = priority;                                            \
  202.             collapse        = i;                                                \
  203.         }                                                                        \
  204.     }                                                                            \
  205.     i = collapse;                                                                \
  206.     inVM.DoOp( i, oper[ i ] & 0xFF );                                            \
  207.     numExps--;                                                                    \
  208.     oper[ i ] = oper[ i+1 ];                                                    \
  209.     for ( i++; i < numExps; i++ ) {                                                \
  210.         inVM.MoveUp( i );                                                        \
  211.         oper[ i ] = oper[ i+1 ];                                                \
  212.     }
  213.  
  214.  
  215.  
  216. //    Pre:    All whitespace and illegal chars are removed
  217. //    Pre:    Parens balence & all letters are capitalized
  218. //    Note:    I normally don't write such huge, non-compartmentalized code, but speed is important
  219. void Expression::Compile( char* inStr, long inLen, const Hashtable& inDict, ExprVirtualMachine& inVM ) {
  220.     bool            hasLetters = false;
  221.     double*            dblPtr, val;
  222.     long            highestPriority, priority, i, numExps = 0, startPos = 0;
  223.     long            fcnCall, collapse, c, pos, parens = 0, firstParen = -1;
  224.     short            oper[ 4 ];
  225.     short            reg[ 4 ];
  226.     
  227.     // Catch a negated expression
  228.     if ( inLen > 0 && *inStr == '-' ) {
  229.         inVM.Loadi( 0.0 );
  230.         oper[ 0 ] = 0x100 | '-';
  231.         numExps = 1;
  232.         inStr++;
  233.         inLen--;
  234.     }
  235.             
  236.     // Make a pass thru of the string, finding the starts and ends of all root exprs
  237.     for ( pos = 0; pos < inLen; pos++ ) {
  238.         c = inStr[ pos ];
  239.         
  240.         if ( c == '(' ) {
  241.             if ( firstParen < 0 )
  242.                 firstParen = pos;
  243.             parens++;  }
  244.         else if ( c == ')' )
  245.             parens--;
  246.     
  247.         // Don't consider any chars if we're not at the root level        
  248.         if ( parens == 0 ) {
  249.             
  250.             if ( c >= 'A' && c <= 'Z' )
  251.                 hasLetters = true;
  252.         
  253.             // Operators are what separate exprs
  254.             switch ( c ) {    
  255.                 case '-':
  256.                 case '+':    priority = 0x0100;    goto doOp;
  257.                 case '/':
  258.                 case '%':
  259.                 case '*':    priority = 0x0200;    goto doOp;
  260.                 case '^':    priority = 0x0300;
  261.  
  262.                     // Close cur expr    
  263. doOp:                if ( pos > startPos && pos + 1 < inLen ) {
  264.  
  265.                         // Push registers 0 thru (numExps-1), the registers in use
  266.                         inVM.MassPush( numExps - 1 );
  267.                             
  268.                         // Recurse
  269.                         Compile( inStr + startPos, pos - startPos, inDict, inVM );
  270.                         oper[ numExps ] = c | priority;
  271.                         numExps++;
  272.                         startPos = pos + 1;
  273.                         
  274.                         // The return value is in reg 0. Also pop/restore the FP registers in use
  275.                         inVM.Move( numExps - 1 );
  276.                         inVM.MassPop( numExps - 2 );
  277.  
  278.                         // 4 exprs, given three priority operators, 4 exprs guaruntees we can collapse two into one expr
  279.                         if ( numExps == 4 ) {
  280.                             __collapseTwo
  281.                         }
  282.                     }
  283.             }
  284.         }
  285.     }
  286.  
  287.  
  288.     // Detect base case (ie, whole string is an expr)
  289.     if ( numExps == 0 ) {
  290.             
  291.         // See if we found a fcn call or an unneeded paren pair: (...)
  292.         if ( firstParen >= 0 && firstParen <= 4 ) {
  293.  
  294.             // Eval what's inside the parens
  295.             Compile( inStr + firstParen + 1, inLen - firstParen - 2, inDict, inVM );
  296.             
  297.             // Translate the string of the fcn to a (one byte) code number
  298.             fcnCall = *((long*) inStr);
  299.             switch ( fcnCall ) {
  300.                 #if EG_MAC
  301.                 case 'SQRT':    fcnCall = cSQRT;        break;
  302.                 case 'ATAN':    fcnCall = cATAN;        break;
  303.                 case 'ABS(':    fcnCall = cABS;            break;
  304.                 case 'SIN(':    fcnCall = cSIN;            break;
  305.                 case 'COS(':    fcnCall = cCOS;            break;
  306.                 case 'TAN(':    fcnCall = cTAN;            break;
  307.                 case 'LOG(':    fcnCall = cLOG;            break;
  308.                 case 'EXP(':    fcnCall = cEXP;            break;
  309.                 case 'SQR(':    fcnCall = cSQR;            break;
  310.                 case 'SQWV':    fcnCall = cSQWV;        break;
  311.                 case 'POS(':    fcnCall = cPOS;            break;
  312.                 case 'RND(':    fcnCall = cRND;            break;
  313.                 #elif EG_WIN
  314.                 case 'TRQS':    fcnCall = cSQRT;        break;
  315.                 case 'NATA':    fcnCall = cATAN;        break;
  316.                 case '(SBA':    fcnCall = cABS;            break;
  317.                 case '(NIS':    fcnCall = cSIN;            break;
  318.                 case '(SOC':    fcnCall = cCOS;            break;
  319.                 case '(NAT':    fcnCall = cTAN;            break;
  320.                 case '(GOL':    fcnCall = cLOG;            break;
  321.                 case '(PXE':    fcnCall = cEXP;            break;
  322.                 case '(RQS':    fcnCall = cSQR;            break;
  323.                 case 'VWQS':    fcnCall = cSQWV;        break;
  324.                 case '(SOP':    fcnCall = cPOS;            break;
  325.                 case '(DNR':    fcnCall = cRND;            break;
  326.                 #endif
  327.                 default:        fcnCall    = 0;            break;
  328.             }
  329.             inVM.MathOp( fcnCall );  }
  330.         
  331.         // Catch the case where we have a number/immediate
  332.         else if ( ! hasLetters ) {
  333.             val = UtilStr::GetFloatVal( inStr, inLen );  
  334.             inVM.Loadi( val ); }
  335.             
  336.         // At this point we assume it's an identifier, so we'll look up its value
  337.         else {
  338.             UtilStr temp;
  339.             temp.Assign( inStr, inLen );
  340.             if ( inDict.Get( &temp, &dblPtr ) )
  341.                 inVM.Loadi( dblPtr );
  342.         } }
  343.         
  344.     // If there more than one expression
  345.     else {
  346.     
  347.         // Push registers 0 thru (numExps-1), the registers in use
  348.         inVM.MassPush( numExps - 1 );
  349.             
  350.         // Finish the current expr
  351.         if ( startPos < inLen ) {
  352.             Compile( inStr + startPos, inLen - startPos, inDict, inVM );
  353.             numExps++;
  354.         }
  355.         
  356.         // The return value is in reg 0. Also pop/restore the FP registers in use
  357.         inVM.Move( numExps - 1 );
  358.         inVM.MassPop( numExps - 2 );
  359.  
  360.         // When there'll be no more exprs, we're free to collapse all the exprs into one
  361.         while ( numExps > 1 ) {
  362.             __collapseTwo
  363.         }
  364.  
  365.     }
  366.                 
  367.     // Register 0 is the return value by convention
  368. }
  369.  
  370.  
  371. */
  372.  
  373.  
  374.  
  375.  
  376. bool Expression::IsDependent( char* inStr ) {
  377.      long pos, len = 0, c;
  378.      
  379.      while ( inStr[ len ] ) 
  380.          len++;
  381.      
  382.      pos = mEquation.contains( inStr, len, 0, false );
  383.      while ( pos > 0 ) {
  384.      
  385.          // This expr is depndent on inStr when we find a substring match that *isn't* a substring of another identifier
  386.          c = mEquation.getChar( pos - 1 );
  387.          if ( c < 'A' || c > 'Z' ) {
  388.              c = mEquation.getChar( pos + len );
  389.              if ( c < 'A' || c > 'Z' )
  390.                  return true;
  391.          }    
  392.          pos = mEquation.contains( inStr, len, pos, false );
  393.      }
  394.      
  395.      return false;
  396. }
  397.  
  398.  
  399.  
  400.  
  401. bool Expression::Weight( Expression& inExpr, float* inTransitionLink ) {
  402.  
  403.     if ( mIsCompiled && inExpr.mIsCompiled ) {
  404.         Chain( inExpr, inTransitionLink );
  405.         return true; }
  406.     else
  407.         return false;
  408. }
  409.  
  410.  
  411.  
  412.  
  413. void Expression::Assign( Expression& inExpr ) {
  414.  
  415.     mEquation.Assign( inExpr.mEquation );
  416.     mIsCompiled = inExpr.mIsCompiled;
  417.  
  418.     if ( inExpr.mIsCompiled )
  419.         ExprVirtualMachine::Assign( inExpr );
  420. }
  421.  
  422.  
  423.  
  424.  
  425. bool Expression::Compile( const UtilStr& inStr, ExpressionDict& inDict ) {
  426.     int i, c, parens, len;
  427.     
  428.     mEquation.Assign( inStr );
  429.     
  430.     // Case insensitive, remove all spaces
  431.     mEquation.Capitalize(); 
  432.     mEquation.Remove( " " );
  433.     mEquation.Remove( "\t" );
  434.     
  435.     // Check for balenced parens
  436.     parens = 0;
  437.     len = mEquation.length();
  438.     for ( i = 1; i <= len && parens >= 0; i++ ) {
  439.         c = mEquation.getChar( i );
  440.         
  441.         switch ( c ) {
  442.             case '(':    parens++;    break;
  443.             case ')':    parens--;    break;
  444.         }
  445.     }
  446.  
  447.     if ( parens != 0 ) {
  448.         mEquation.Wipe();
  449.         mIsCompiled = false; }
  450.     else {
  451.     
  452.         // Wipe whatever program was in the VM before
  453.         Clear();
  454.         
  455.         if ( len > 0 ) {
  456.         
  457.             // Generate insts for the VM that evaluate mEquation
  458.             int retRegNum = Compile( mEquation.getCStr(), mEquation.length(), inDict, *this );
  459.             Move( retRegNum, 0 );  }
  460.         else {
  461.         
  462.             // Color register 0 as used
  463.             AllocReg();
  464.             
  465.             // If the expression is blank, make it return 0
  466.             Loadi( 0.0, 0 );
  467.         }
  468.         
  469.         
  470.         PrepForExecution();
  471.         mIsCompiled = true;
  472.     }
  473.         
  474.     return mIsCompiled;
  475. }
  476.  
  477.  
  478.